package cn.dglydrpy.study.algorithm.od;

import java.util.*;

/**
 * @author Yyy
 * @date 2024/11/8 18:24
 * @description
 * 给定一个矩阵，包含 N×M 个整数，以及一个包含 K 个整数的数组。
 * 输入描述：
 * 第一行输入两个正整数 N 和 M，表示矩阵大小。
 * 接下来 N 行 M 列表示矩阵内容。
 * 下一行包含一个正整数 K。
 * 下一行包含 K 个整数，表示所需包含的数组，K 个整数可能存在重复数字。所有输入数据小于 1000。
 * 输出描述：输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出 -1。
 * 补充说明：示例中展示了如何根据输入的矩阵和数组找到满足条件的子矩阵的最小宽度。例如在一个例子中，矩阵的某些列包含了给定数组中的所有数字，那么这些列构成的子矩阵的宽度就是所求的结果。如果找不到满足条件的子矩阵，则输出 -1
 输入：
2 5
1 2 2 3 1
1 3 2 3 4
3
1 1 4
输出：
5 
 */
public class Od0029_MinMatrixWeight {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String[] s = scanner.nextLine().split(" ");
            int M = Integer.valueOf(s[0]);
            int N = Integer.valueOf(s[1]);
            int[][] arr = new int[M][N];
            for(int i=0;i<M;i++){
                String[] split = scanner.nextLine().split(" ");
                for(int j=0;j<N;j++){
                    arr[i][j] = Integer.valueOf(split[j]);
                }
            }
            
            int K = Integer.valueOf(scanner.nextLine());
            int[] brr = new int[K];
            String[] s1 = scanner.nextLine().split(" ");
            for(int i=0;i<K;i++){
                brr[i] = Integer.valueOf(s1[i]);
            }
            
            int ans = myAnswer(arr,brr);
            System.out.println(ans);

            int answer1 = answer1(arr,brr);
            System.out.println(answer1);
            
        }
    }

    private static int myAnswer(int[][] arr, int[] brr) {
        if(arr == null || arr.length == 0 || arr[0].length == 0){
            return -1;
        }
        
        // 目标词频缓存
        Map<Integer,Integer> map = new HashMap<>();
        for(int b : brr){
            if(map.containsKey(b)){
                map.put(b,map.get(b)+1);
            }else{
                map.put(b,1);
            }
        }
        
        int ans = -1;
        int left = 0;
        int right = arr[0].length-1;

        // 整体判断
        boolean pass = windowsCheck(arr, left, right, map);
        if(!pass){
            return ans;
        }
//        System.out.println("right:" + right + ",left: " + left);
        ans = right - left + 1;
        
        // 移动左边指针
        while(left <= right){
            pass = windowsCheck(arr, left + 1, right, map);
            if(!pass){
                break;
            }else{
                left++;
//                System.out.println("right:" + right + ",left: " + left);
                ans = right - left +1;
            }
        }

        // 移动右边指针
        while(left <= right){
            pass = windowsCheck(arr, left, right - 1, map);
            if(!pass){
                break;
            }else{
                right--;
//                System.out.println("right:" + right + ",left: " + left);
                ans = right - left +1;
            }
        }
        return ans;
    }
    
    private static boolean windowsCheck(int[][] arr, int left, int right, Map<Integer, Integer> map){

        Map<Integer,Integer> tempMap = new HashMap<>(map);
        for(int j=left;j<=right;j++){
            for(int i=0;i<arr.length;i++){
                int key = arr[i][j];
                if(tempMap.containsKey(key)){
                    Integer count = tempMap.get(key);
                    tempMap.put(key,count-1);
                }
            }
        }

        Set<Map.Entry<Integer, Integer>> entries = tempMap.entrySet();
        for(Map.Entry<Integer, Integer> entry : entries){
            if(entry.getValue() > 0){
                return false;
            }
        }
        
        return true;
    };


    public static int answer1(int[][] matrix, int[] brr) {
        HashMap<Integer, int[]> map = new HashMap<>();
        for (int col = 0; col < matrix[0].length; col++) {
            int[] cols = new int[matrix.length];
            for (int row = 0; row < matrix.length; row++) {
                cols[row] = matrix[row][col];
            }
            map.put(col, cols);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < map.keySet().size(); i++) {
            int[] rest = brr;
            int j = i;
            while (j < map.keySet().size()) {
                rest = diff(rest, map.get(j));
                if (rest.length == 0) {
                    break;
                }
                j++;
            }
            if (rest.length == 0) {
                ans.add(new Integer(j - i));
            } else {
                ans.add(new Integer(map.keySet().size() + map.keySet().size()));
            }
        }
        int min = Integer.MAX_VALUE;
        for (Integer an : ans) {
            min = Math.min(min, an.intValue());
        }
        if (min > map.keySet().size()) {
            return -1;
        }
        return min;
    }

    public static int[] diff(int[] arr1, int[] arr2) {
        ArrayList<Integer> list2 = new ArrayList<>();
        for(int v : arr2){
            list2.add(v);
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (Integer value : arr1) {
            if (list2.contains(value)) {
                res.add(value);
            } else {
                list2.remove(value);
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}
